#include <string>
#include <vector>
using namespace std;
// tire 树的解法
class MagicDictionary
{
private:
    struct tire_node
    {
        tire_node(char c = '\0') : ch(c), sons(26, nullptr) { ; }
        tire_node *get_son(const char c)
        {
            return sons[c - 'a'];
        }
        tire_node *create_son(const char c)
        {
            return sons[c - 'a'] = new tire_node(c);
        }
        void add_end()
        {
            end_num++;
        }
        size_t get_end_num()
        {
            return end_num;
        }

    private:
        char ch;
        int end_num = 0;
        tire_node *next = nullptr;
        vector<tire_node *> sons;
    };
    class tire_tree
    {
    public:
        void insert(const string &str)
        {
            tire_node *cur = _root;
            for (auto e : str)
            {
                tire_node *son = cur->get_son(e);
                if (!son)
                    son = cur->create_son(e);
                cur = son;
            }
            cur->add_end();
        }
        bool normol_serach(tire_node *root, const string &str)
        {
            tire_node *cur = root;
            for (auto e : str)
            {
                tire_node *son = cur->get_son(e);
                if (!son)
                    return false;
                cur = son;
            }
            return cur->get_end_num() != 0;
        }
        bool second_serach(tire_node *cur, const string &str, const size_t i)
        {
            string new_serach_str(str.substr(i));
            for (char ch = 'a'; ch <= 'z'; ch++)
            {
                if (ch == str[i])
                    continue;
                new_serach_str.front() = ch;
                if (normol_serach(cur, new_serach_str))
                    return true;
            }
            return false;
        }
        bool serach_word(string &str)
        {
            tire_node *cur = _root;
            for (int i = 0; i < str.size(); i++)
            {
                if (second_serach(cur, str, i))
                    return true;
                tire_node *son = cur->get_son(str[i]);
                if (!son)
                    return false;
                cur = son;
            }
            return false;
        }

    private:
        tire_node *_root = new tire_node(0);
    };
    tire_tree tire;

public:
    /** Initialize your data structure here. */
    MagicDictionary()
    {
        ;
    }

    void buildDict(vector<string> dictionary)
    {
        for (auto &e : dictionary)
            tire.insert(e);
    }

    bool search(string searchWord)
    {
        return tire.serach_word(searchWord);
    }
};
// 哈希表加数不同 把相同长度的归类在一起
#include <unordered_map>
class MagicDictionary
{
private:
    unordered_map<size_t, vector<string>> len_map;

public:
    /** Initialize your data structure here. */
    MagicDictionary()
    {
    }

    void buildDict(vector<string> dictionary)
    {
        for (auto &word : dictionary)
            len_map[word.size()].push_back(std::move(word));
    }

    bool search(string searchWord)
    {
        for (auto &word : len_map[searchWord.size()])
        {
            size_t diff_count(0);
            for (size_t i = 0; i < searchWord.size() && diff_count < 2; i++)
                if (searchWord[i] != word[i])
                    diff_count++;
            if (diff_count == 1)
                return true;
        }
        return false;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */
/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */